package cn.xuchunh.exam;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 输入一个完全图的邻接矩阵，求最短遍历各点的最短路
 * Created by XuChunH on 2016/9/17.
 */
public class ShortestPath {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.valueOf(scanner.nextLine());
        int[][] matrix = new int[n][n];
        for (int i = 0; i < n; i++) {
            String[] rows = scanner.nextLine().split(",");
            for (int j = 0; j < n; j++) {
                matrix[i][j] = Integer.valueOf(rows[j]);
            }
        }
        List<Integer> list = new ArrayList<>();
        int distance = 0;
        for (int i = 0; i < n; i++) {
            int distance1 = 0;
            for (int j = 0; j < n; j++) {
                list.add(j);
            }
            int start = i;
            list.remove(new Integer(i));
            int temp;
            int min;
            while (!list.isEmpty()){
                temp = list.get(0);
                min = matrix[start][temp];
                for (Integer dest : list) {
                    if(min > matrix[start][dest]){
                        min = matrix[start][dest];
                        temp = dest;
                    }
                }
                start = temp;
                list.remove(new Integer(start));
                distance1 += min;
            }
            if(distance !=0) {
                distance = distance1 < distance ? distance1 : distance;
            }else {
                distance = distance1;
            }
        }

        System.out.println(distance);
    }
}
